// 插入排序,对数组Arr进行插入排序。
function insertionSort(Arr) {
  // 从数组的第二个元素开始，向i之前的项中插入Arr[i]值
  for (let i = 1; i < Arr.length; i++) {
    insert(Arr, i, Arr[i]);
  }
}
// 将value插入到Arr数组中
function insert(Arr, idx, value) {
  let p = idx - 1;
  // 如果被插入的值value小于前面p位置值，则把p位置中的值（大值）往后移动一位。
  while (Arr[p] > value && p >= 0) {
    Arr[p + 1] = Arr[p]; // 把数组中p位置的值，往后移动一位
    p--; // p索引值递减
  }
  Arr[p + 1] = value;
}
let arr = [1, 45, 3,  67, 8, 9, 100];
insertionSort(arr);
exports.insertionSort = insertionSort;